#ifndef __PARSER_TYPES_CPP__
#define __PARSER_TYPES_CPP__

#include "lzjlex/lzjlex.cpp"
#include <exception>
#include <map>
#include <memory>
#include <set>
#include <stack>
#include <unordered_set>
#include <vector>

using std::make_shared;
using std::map;
using std::shared_ptr;
using std::stack;
using std::unordered_map;
using std::unordered_set;
using std::vector;

class RuleType;        // 规则类型
class LRItem;          // 一个LR1项目
enum class ActionType; // 分析表动作类型
class ParseException;  // 分析错误
class Action;          // 分析表动作
class ParseTreeNode;   // 分析树节点
class ASTNode;         // AST节点

using PtrASTNode = shared_ptr<ASTNode>;
using PtrParseTreeNode = shared_ptr<ParseTreeNode>;
using PtrAction = shared_ptr<Action>;

class RuleType : GrammarT {
public:
    bool isTerminal() override { return false; }
    static vector<string> ruleNames; // TODO stupid
    string getName() { return RuleType::ruleNames[lhs]; }
    // 该规则在rules数组中的下标
    int index;
    // 该规则名称在symbols数组中的下标
    int lhs;
    // 该规则包含的子规则和终结符在symbols数组中的下标
    vector<int> rhs;
    RuleType(){};
    RuleType(int index) : index(index) {}
    bool operator==(const RuleType &t) const {
        return index == t.index && lhs == t.lhs && rhs == t.rhs;
    }
    bool operator!=(const RuleType &t) const { return !(*this == t); }
    bool operator<(const RuleType &item) const {
        if (index != item.index) {
            return index < item.index;
        } else if (lhs != item.lhs) {
            return lhs < item.lhs;
        } else {
            return rhs < item.rhs;
        }
    }
};

vector<string> RuleType::ruleNames = vector<string>();

class LRItem {
public:
    RuleType rule;
    int position;
    int lookahead;
    LRItem() = default;
    LRItem(RuleType rule, int position, int lookahead)
        : rule(rule), position(position), lookahead(lookahead){};
    int getExpectedSymbol() {
        if (position >= rule.rhs.size())
            return -1;
        return rule.rhs.at(position);
    }
    bool operator==(const LRItem &item) const {
        return rule == item.rule && position == item.position && lookahead == item.lookahead;
    }
    bool operator!=(const LRItem &item) const { return !(*this == item); }
    bool operator<(const LRItem &item) const {
        if (rule != item.rule) {
            return rule < item.rule;
        } else if (position != item.position) {
            return position < item.position;
        } else {
            return lookahead < item.lookahead;
        }
    }
};

class ParseException : std::exception {
public:
    int linePos;
    int charPos;
    string msg;
    ParseException() = default;
    ParseException(int linePos, int charPos, string msg)
        : linePos(linePos), charPos(charPos), msg(msg) {}
};

enum class ActionType { UNDEFINED, ACCEPT, SHIFT, REDUCE, CONFLICT, ERROR };

class Action {
public:
    ActionType atype;
    int state;
    ParseException parseException;
    RuleType rule;
    vector<PtrAction> actions;
    Action() : atype(ActionType::UNDEFINED) {}
    Action(bool) : atype(ActionType::ACCEPT) {}
    Action(int state) : atype(ActionType::SHIFT), state(state) {}
    Action(RuleType rule) : atype(ActionType::REDUCE), rule(rule) {}
    Action(ParseException e) : atype(ActionType::ERROR), parseException(e) {}
    ~Action() {}
    void addAction(const Action &a) {
        if (atype != ActionType::CONFLICT)
            actions = vector<PtrAction>();
        actions.push_back(make_shared<Action>(a));
    }
    friend std::ostream &operator<<(std::ostream &oss, Action &a) {
        switch (a.atype) {
        case ActionType::UNDEFINED:
            oss << "-";
            break;
        case ActionType::SHIFT:
            oss << "s" << a.state;
            break;
        case ActionType::REDUCE:
            oss << "r" << a.rule.index;
            break;
        case ActionType::ACCEPT:
            oss << "ACC";
            break;
        case ActionType::CONFLICT:
            for (auto i : a.actions) {
                oss << i << "/";
            }
            oss << "\b";
            break;
        default:
            oss << "WTF";
        }
        return oss;
    }
    bool operator==(const Action &a) const {
        if (atype != a.atype)
            return false;
        switch (atype) {
        case ActionType::ACCEPT:
        case ActionType::UNDEFINED:
            return true;
        case ActionType::SHIFT:
            return state == a.state;
        case ActionType::REDUCE:
            return rule == a.rule;
        case ActionType::CONFLICT:
        case ActionType::ERROR:
            return false;
        default:
            cout << "\n\nMiss a condition in Action operator==!!!\n\n";
            exit(0);
        }
    }
    bool operator!=(const Action &b) const { return !(*this == b); }

private:
    void copyFields(const Action &a) {
        atype = a.atype;
        switch (atype) {
        case ActionType::UNDEFINED:
        case ActionType::ACCEPT:
            break;
        case ActionType::REDUCE:
            rule = RuleType();
            rule = a.rule;
            break;
        case ActionType::SHIFT:
            state = a.state;
            break;
        case ActionType::CONFLICT:
            actions = vector<PtrAction>();
            actions = a.actions;
            break;
        case ActionType::ERROR:
            parseException = ParseException();
            parseException = a.parseException;
            break;
        default: // should never reach
            cout << "Miss a condition in copyfields!";
            exit(0);
        }
    }
};


class ParseTreeNode {
public:
    union {
        RuleType ruleT;
        Token token;
    };
    deque<PtrParseTreeNode> children;

    bool isTerminal() { return children.empty(); }
    ParseTreeNode() {}
    ParseTreeNode(RuleType ruleT, deque<PtrParseTreeNode> children)
        : ruleT(ruleT), children(children){};
    ParseTreeNode(Token token) : token(token){};
    ~ParseTreeNode() {}
};

class ASTNode {
public:
    static unordered_set<string> ignoredTerminals;
    static unordered_set<string> childToSibling;
    static unordered_map<string, string> generalization;
    static unordered_set<string> compressExclusion;
    static unordered_map<string, string> terminalNameMap;
    static unordered_set<string> childToFields;
    static unordered_set<string> mergeChilds;
public:
    string name;
    unordered_map<string, vector<Token>> fields;
    vector<PtrASTNode> children;
    ASTNode() = default;
    // ~ASTNode() { cout << "Destruct ASTNode " << name << endl; }
    static PtrASTNode buildAST(PtrParseTreeNode p) {
        PtrASTNode ast = buildASTStep1_rawAST(p);
        cout << "Finish step 1\n";
        ASTNode::buildASTStep2_child2Field(ast);
        cout << "Finish step 2\n";
        ASTNode::buildASTStep3_child2Sibling(ast);
        cout << "Finish step 3\n";
        ASTNode::buildASTStep4_mergeChilds(ast);
        cout << "Finish step 4\n";
        cout << "Finish build AST;\n";
        return ast;
    }

private:
    static PtrASTNode buildASTStep1_rawAST(PtrParseTreeNode p) { // 第一步，建立AST
        PtrASTNode ast = make_shared<ASTNode>();
        vector<PtrASTNode> newChildren;
        ast->name = p->ruleT.getName();
        for (auto i : p->children) {
            if (!i->isTerminal()) { // 递归
                newChildren.push_back(buildASTStep1_rawAST(i));
            } else if (!ASTNode::ignoredTerminals.count(i->token.getName())) {
                // 把不可删除的终结符提升到树根
                if (ast->fields.count(terminalNameMap.at(i->token.getName()))) {
                    ast->fields.at(terminalNameMap.at(i->token.getName())).push_back(i->token);
                } else {
                    ast->fields[terminalNameMap.at(i->token.getName())] = {i->token};
                }
            }
        }
        if(generalization.count(p->ruleT.getName())){
            if (newChildren.size() == 1 && !ASTNode::compressExclusion.count(p->ruleT.getName())) {
                return newChildren[0];
            }
            ast->name = generalization.at(p->ruleT.getName());
        }
        ast->children = newChildren;
        return ast;
    }
    static void buildASTStep2_child2Field(PtrASTNode ast) { // 第二步，child to fields
        vector<PtrASTNode> newChildren;
        for (auto i : ast->children) {
            if(i->children.empty() && childToFields.count(i->name)){ // 压缩
                ast->fields.insert(i->fields.begin(), i->fields.end());
            } else{
                newChildren.push_back(i);
                buildASTStep2_child2Field(i);
            }
        }
        ast->children = newChildren;
    }
    static vector<PtrASTNode> buildASTStep3_child2Sibling(PtrASTNode ast){ // 第三步，child to sibling
        vector<PtrASTNode> other2bElevate; // 其它类型递归节点的养父
        vector<PtrASTNode> self2bElevate;  // 自己类型递归节点的养父
        vector<PtrASTNode> newChildren;
        unordered_set<string> recursiveChildNames;
        bool hasRecursiveChild = false;
        for (auto i:ast->children) {
            auto&& tmp = buildASTStep3_child2Sibling(i);    // 获得孩子的养父
            if (ASTNode::childToSibling.count(i->name)) { // 是要被提升的
                hasRecursiveChild = true;
                recursiveChildNames.insert(i->name);
                if (ast->name != i->name) {
                    other2bElevate.insert(other2bElevate.end(), tmp.begin(), tmp.end());
                } else {
                    self2bElevate.insert(self2bElevate.end(), tmp.begin(), tmp.end());
                }
            } else {
                newChildren.push_back(i);
            }
        }
        newChildren.insert(newChildren.end(), other2bElevate.rbegin(), other2bElevate.rend());
        ast->children = newChildren;
        if (ASTNode::childToSibling.count(ast->name)) { // 自己就是在递归
            self2bElevate.push_back(ast);
            return self2bElevate;
        } 
        return {};
    }

    static void buildASTStep4_mergeChilds(PtrASTNode ast){
        unordered_map<string, PtrASTNode> stepFathers; // <节点类型，节点的孩子>
        vector<PtrASTNode> newChildren;
        for(auto i: ast->children){
            buildASTStep4_mergeChilds(i);
            if(ASTNode::mergeChilds.count(i->name)){
                if(!stepFathers.count(i->name)){
                    stepFathers[i->name] = make_shared<ASTNode>();
                }
                stepFathers[i->name]->children.insert(stepFathers[i->name]->children.end(),
                                                      i->children.begin(), i->children.end());
            } else {
                newChildren.push_back(i);
            }
        }
        for(auto [name, father]: stepFathers){
            father->name = name;
            newChildren.push_back(father);
        }
        ast->children = newChildren;
    }
};

unordered_set<string> ASTNode::ignoredTerminals = unordered_set<string>();
unordered_set<string> ASTNode::childToSibling = unordered_set<string>();
unordered_map<string, string> ASTNode::generalization = unordered_map<string, string>();
unordered_set<string> ASTNode::compressExclusion = unordered_set<string>();
unordered_map<string, string> ASTNode::terminalNameMap = unordered_map<string, string>();
unordered_set<string> ASTNode::childToFields = unordered_set<string>();
unordered_set<string> ASTNode::mergeChilds = unordered_set<string>();



#endif